package lu.uni.adtool.adtconverter;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.EnumMap;
import java.util.List;

import lu.uni.adtool.adtconverter.enums.NodeType;
import lu.uni.adtool.adtconverter.enums.PathType;
import lu.uni.adtool.adtconverter.enums.StratType;

/**
 * Stores all needed information about a single tree in several indeces.
 * 
 * @author Mateusz Pawlik modified by Piotr Kordy
 */
public class InfoTree
{
  private LblTree           inputTree;




  /**
   *  Dictionary with labels - common for two input trees.
   */
  private LabelDictionary   ld;

  /**
   * Store the type of a node: for every node stores three boolean values (L, R,
   * H).
   */
  private EnumMap<NodeType,boolean[]>  nodeType;

  /**
   * Paths and rel subtrees are inside 2D arrays to be able to get them by
   * paths/relsubtrees[L/R/H][node]/size.
   */
  private EnumMap<NodeType,int[]> paths;
  /**
   * rel subtrees.
   */
  private EnumMap<NodeType,int[][]> relSubtrees;
  /**
   * An array with all the indices of size [16][treeSize].
   */
  private EnumMap<PathType,int[]> info;
  private LblTree[] post2nodes;
  /**
   * Strategy for Demaine (is there sth on the left/right of the heavy node).
   */
  private StratType[] postStrategy;

  // temporal variables
  /**
   * Temporal value of size of a subtree.
   */
  private int               sizeTmp          = 0;
  /**
   * Temporal value of sum of descendat sizes.
   */
  private int               descSizesTmp     = 0;
  /**
   * Temporal value of sum of key roots sizes.
   */
  private int               krSizesSumTmp    = 0;
  /**
   * Temporal value of sum of reversed key roots sizes.
   */
  private int               revkrSizesSumTmp = 0;
  /**
   * Temporal value of preorder.
   */
  private int               preorderTmp      = 0;

  /**
   * Remembers what is the current node's postorder (current in the TED
   * recursion).
   */
  private int               currentNode      = -1;

  /**
   * Remembers if the trees order was switched during the recursion (in
   * comparison with the order of input trees).
   */
  private boolean           switched         = false;

  /**
   * Number of leafs.
   */
  private int               leafCount        = 0;
  /**
   * Tree size.
   */
  private int               treeSize         = 0;

  /**
   * Creates an InfoTree object, gathers all information about aInputTree and
   * stores in indexes.
   * aInputTree is not needed any more.
   * Remember to pass the same LabelDictionary object to both trees which are
   * compared.
   * 
   * @param aInputTree
   *          an LblTree object
   * @param aLd
   *          a LabelDictionary object
   */
  public InfoTree(final LblTree aInputTree,final LabelDictionary aLd)
  {
    this.inputTree = aInputTree;
    treeSize = inputTree.getNodeCount();
    this.info = new EnumMap<PathType,int[]>(PathType.class);
    //enumValue.ordinal()  EnumClass.values()[ordinal]
    //int[16][treeSize];
    info.put(PathType.POST2_SIZE,new int[treeSize]);
    info.put(PathType.POST2_KR_SUM,new int[treeSize]);
    info.put(PathType.POST2_REV_KR_SUM,new int[treeSize]);
    info.put(PathType.POST2_DESC_SUM,new int[treeSize]);
    info.put(PathType.POST2_PRE,new int[treeSize]);
    info.put(PathType.POST2_PARENT,new int[treeSize]);
    post2nodes = new LblTree[treeSize];
    info.put(PathType.POST2_LLD,new int[treeSize]);

    info.put(PathType.POST2_MIN_KR,new int[treeSize]);
    info.put(PathType.RPOST2_RLD,new int[treeSize]);
    info.put(PathType.RPOST2_MIN_RKR,new int[treeSize]);
    info.put(PathType.RPOST2_POST,new int[treeSize]);
    info.put(PathType.PRE2_POST,new int[treeSize]);

    Arrays.fill(info.get(PathType.POST2_PARENT), -1);
    Arrays.fill(info.get(PathType.POST2_MIN_KR), -1);
    Arrays.fill(info.get(PathType.RPOST2_MIN_RKR), -1);
    Arrays.fill(info.get(PathType.POST2_LLD), 0);

    postStrategy = new StratType[treeSize];
    Arrays.fill(postStrategy, StratType.NONE);

    //Arrays.fill(info[POST2_PARENT], -1);
    //Arrays.fill(info[POST2_MIN_KR], -1);
    //Arrays.fill(info[RPOST2_MIN_RKR], -1);
    //Arrays.fill(info[POST2_STRATEGY], -1);
    this.paths = new EnumMap<NodeType,int[]>(NodeType.class);
    this.paths.put(NodeType.LEFT,new int[treeSize]);
    Arrays.fill(this.paths.get(NodeType.LEFT), -1);
    this.paths.put(NodeType.RIGHT,new int[treeSize]);
    Arrays.fill(this.paths.get(NodeType.RIGHT), -1);
    this.paths.put(NodeType.HEAVY,new int[treeSize]);
    Arrays.fill(this.paths.get(NodeType.HEAVY), -1);
    
    this.relSubtrees = new EnumMap<NodeType,int[][]>(NodeType.class);
    relSubtrees.put(NodeType.HEAVY,new int[treeSize][]);
    relSubtrees.put(NodeType.RIGHT,new int[treeSize][]);
    relSubtrees.put(NodeType.LEFT,new int[treeSize][]);
    this.nodeType = new EnumMap<NodeType,boolean[]>(NodeType.class);
    nodeType.put(NodeType.HEAVY,new boolean[treeSize]);
    nodeType.put(NodeType.RIGHT,new boolean[treeSize]);
    nodeType.put(NodeType.LEFT,new  boolean[treeSize]);
    this.ld = aLd;
    this.currentNode = treeSize - 1;
    gatherInfo(inputTree, -1);
    postTraversalProcessing();
  }

  /**
   * Returns the size of the tree.
   * 
   * @return tree size.
   */
  public final int getSize()
  {
    return treeSize;
  }

  /**
   * For given infoCode returns an info array (index array).
   * 
   * @param infoCode type of info
   * @return array with requested index
   */
  public final int[] getInfo(final PathType infoCode)
  {
    return info.get(infoCode);
  }


  /**
   * Gathers information of a given tree in corresponding arrays.
   * 
   * At this point the given tree is traversed once, but there is a loop over
   * current nodes children
   * to assign them their parents.
   * 
   * @param aT a tree
   * @param postorder postorder
   * @return
   */
  private int gatherInfo(final LblTree aT, final int newPostorder)
  {
    int postorder = newPostorder;
    final int preorder = preorderTmp;
    int currentSize = 0;
    int descSizes = 0;
    int krSizesSum = 0;
    int revkrSizesSum = 0;

    int heavyChild = -1;
    int leftChild = -1;
    int rightChild = -1;
    int weight = -1;
    int maxWeight = -1;
    int currentPostorder = -1;
    int oldHeavyChild = -1;

    ArrayList<Integer> heavyRelSubtreesTmp = new ArrayList<Integer>();
    ArrayList<Integer> leftRelSubtreesTmp = new ArrayList<Integer>();
    ArrayList<Integer> rightRelSubtreesTmp = new ArrayList<Integer>();

    ArrayList<Integer> childrenPostorders = new ArrayList<Integer>();

    preorderTmp++;

    // enumerate over children of current node
    for (int childrenCount = 1; childrenCount <= aT.getChildren().size();
        ++childrenCount) {
      final LblTree child = (LblTree) aT.getChildren().elementAt(
          childrenCount - 1);
      postorder = gatherInfo(child, postorder);
      childrenPostorders.add(postorder);

      currentPostorder = postorder;

      // heavy path
      weight = sizeTmp + 1;
      if (weight >= maxWeight) {
        maxWeight = weight;
        oldHeavyChild = heavyChild;
        heavyChild = currentPostorder;
      }
      else {
        heavyRelSubtreesTmp.add(currentPostorder);
      }
      if (oldHeavyChild != -1) {
        heavyRelSubtreesTmp.add(oldHeavyChild);
        oldHeavyChild = -1;
      }

      // left path
      if (childrenCount == 1) {
        leftChild = currentPostorder;
      }
      else {
        leftRelSubtreesTmp.add(currentPostorder);
      }

      // right path
      rightChild = currentPostorder;
      if (childrenCount < aT.getChildren().size()) {
        rightRelSubtreesTmp.add(currentPostorder);
      }

      // subtree size
      currentSize += 1 + sizeTmp;

      descSizes += descSizesTmp;

      if (childrenCount > 1) {
        krSizesSum += krSizesSumTmp + sizeTmp + 1;
      }
      else {
        krSizesSum += krSizesSumTmp;
        nodeType.get(NodeType.LEFT)[currentPostorder] = true;
      }

      if (childrenCount < aT.getChildren().size()) {
        revkrSizesSum += revkrSizesSumTmp + sizeTmp + 1;
      }
      else {
        revkrSizesSum += revkrSizesSumTmp;
        nodeType.get(NodeType.RIGHT)[currentPostorder] = true;
      }
    }

    postorder++;

    // postorder
    aT.setTmpData(postorder);

    final int currentDescSizes = descSizes + currentSize + 1;
    info.get(PathType.POST2_DESC_SUM)[postorder] = (currentSize + 1)
        * (currentSize + 1 + 3) / 2 - currentDescSizes;
    info.get(PathType.POST2_KR_SUM)[postorder] = krSizesSum + currentSize + 1;
    info.get(PathType.POST2_REV_KR_SUM)[postorder] = revkrSizesSum
        + currentSize + 1;

    // POST2_LABEL
    // labels[rootNumber] = ld.store(aT.getLabel());
    post2nodes[postorder] = aT;

    // POST2_PARENT
    for (Integer i : childrenPostorders) {
      info.get(PathType.POST2_PARENT)[i] = postorder;
    }

    // POST2_SIZE
    info.get(PathType.POST2_SIZE)[postorder] = currentSize + 1;
    if (currentSize == 0) {
      leafCount++;
    }

    // POST2_PRE
    info.get(PathType.POST2_PRE)[postorder] = preorder;

    // PRE2_POST
    info.get(PathType.PRE2_POST)[preorder] = postorder;

    // RPOST2_POST
    info.get(PathType.RPOST2_POST)[treeSize - 1 - preorder] = postorder;

    // heavy path
    if (heavyChild != -1) {
      paths.get(NodeType.HEAVY)[postorder] = heavyChild;
      nodeType.get(NodeType.HEAVY)[heavyChild] = true;

      if (leftChild < heavyChild && heavyChild < rightChild) {
        postStrategy[postorder] = StratType.BOTH;
      }
      else
        if (heavyChild == leftChild) {
          postStrategy[postorder] = StratType.RIGHT;
        }
        else
          if (heavyChild == rightChild) {
            postStrategy[postorder] = StratType.LEFT;
          }
    }
    else {
      postStrategy[postorder] = StratType.RIGHT;
    }

    // left path
    if (leftChild != -1) {
      paths.get(NodeType.LEFT)[postorder] = leftChild;
    }
    // right path
    if (rightChild != -1) {
      paths.get(NodeType.RIGHT)[postorder] = rightChild;
    }

    // heavy/left/right relevant subtrees
    relSubtrees.get(NodeType.HEAVY)[postorder] = toIntArray(heavyRelSubtreesTmp);
    relSubtrees.get(NodeType.RIGHT)[postorder] = toIntArray(rightRelSubtreesTmp);
    relSubtrees.get(NodeType.LEFT)[postorder] = toIntArray(leftRelSubtreesTmp);

    descSizesTmp = currentDescSizes;
    sizeTmp = currentSize;
    krSizesSumTmp = krSizesSum;
    revkrSizesSumTmp = revkrSizesSum;

    return postorder;
  }

  /**
   * Gathers information, that couldn't be collected while tree traversal.
   */
  private void postTraversalProcessing()
  {
    info.put(PathType.KR, new int[leafCount]);
    Arrays.fill(info.get(PathType.KR),0);
    info.put(PathType.RKR, new int[leafCount]);
    Arrays.fill(info.get(PathType.RKR),0);

    final int nc = treeSize;
    final int lc = leafCount;
    int i = 0;


    // compute left-most leaf descendants
    // go along the left-most path, remember each node and assign to it the
    // path's leaf
    // compute right-most leaf descendants (in reversed postorder)
    for (i = 0; i < treeSize; i++) {
      if (paths.get(NodeType.LEFT)[i] == -1) {
        info.get(PathType.POST2_LLD)[i] = i;
      }
      else {
        info.get(PathType.POST2_LLD)[i] = info.get(PathType.POST2_LLD)[paths.get(NodeType.LEFT)[i]];
      }
      if (paths.get(NodeType.RIGHT)[i] == -1) {
        info.get(PathType.RPOST2_RLD)[treeSize - 1
            - info.get(PathType.POST2_PRE)[i]] = (treeSize - 1 - info
            .get(PathType.POST2_PRE)[i]);
      }
      else {
        info.get(PathType.RPOST2_RLD)[treeSize - 1
            - info.get(PathType.POST2_PRE)[i]] = info.get(PathType.RPOST2_RLD)[treeSize
            - 1 - info.get(PathType.POST2_PRE)[paths.get(NodeType.RIGHT)[i]]];
      }
    }

    // compute key root nodes
    // compute reversed key root nodes (in revrsed postorder)
    final boolean[] visited = new boolean[nc];
    final boolean[] visitedR = new boolean[nc];
    Arrays.fill(visited, false);
    int k = lc - 1;
    int kR = lc - 1;
    for (i = nc - 1; i >= 0; i--) {
      if (!visited[info.get(PathType.POST2_LLD)[i]]) {
        info.get(PathType.KR)[k] = i;
        visited[info.get(PathType.POST2_LLD)[i]] = true;
        k--;
      }
      if (!visitedR[info.get(PathType.RPOST2_RLD)[i]]) {
        info.get(PathType.RKR)[kR] = i;
        visitedR[info.get(PathType.RPOST2_RLD)[i]] = true;
        kR--;
      }
    }

    // compute minimal key roots for every subtree
    // compute minimal reversed key roots for every subtree (in reversed
    // postorder)
    int parent = -1;
    int parentR = -1;
    for (i = 0; i < leafCount; i++) {
      parent = info.get(PathType.KR)[i];
      while (parent > -1 && info.get(PathType.POST2_MIN_KR)[parent] == -1) {
        info.get(PathType.POST2_MIN_KR)[parent] = i;
        parent = info.get(PathType.POST2_PARENT)[parent];
      }
      parentR = info.get(PathType.RKR)[i];
      while (parentR > -1 && info.get(PathType.RPOST2_MIN_RKR)[parentR] == -1) {
        info.get(PathType.RPOST2_MIN_RKR)[parentR] = i;
        // get parent's postorder
        parentR = info.get(PathType.POST2_PARENT)[info
            .get(PathType.RPOST2_POST)[parentR]];
        // if parent exists/
        if (parentR > -1) {
          // get its rev. postorder
          parentR = treeSize - 1 - info.get(PathType.POST2_PRE)[parentR];
        }
      }
    }
  }

  /**
   * Transforms a list of Integer objects to an array of primitive int values.
   * 
   * @param integers
   *          list of integers.
   * @return array representation.
   */
  public static final int[] toIntArray(final List<Integer> integers)
  {
    final int[] ints = new int[integers.size()];
    int i = 0;
    for (Integer n : integers) {
      ints[i++] = n;
    }
    return ints;
  }

  /**
   * Gets the nodeType for this instance.
   *
   * @param type type of node
   * @return The nodeType boolean array (L, R ,H).
   */
  public final boolean[] getNodeType(final NodeType type)
  {
    return this.nodeType.get(type);
  }

  /**
   * Gets the inputTree for this instance.
   *
   * @return The inputTree.
   */
  public LblTree getInputTree()
  {
    return this.inputTree;
  }

  /**
   * Sets the post2nodes for this instance.
   *
   * @param post2nodes The post2nodes.
   */
  public void setPost2nodes(LblTree[] post2nodes)
  {
    this.post2nodes = post2nodes;
  }

  /**
   * Sets the post2nodes for this instance.
   *
   * @param index The index to set.
   * @param post2nodes The post2nodes.
   */
  public void setPost2nodes(int index, LblTree post2nodes)
  {
    this.post2nodes[index] = post2nodes;
  }

  /**
   * Gets the post2nodes for this instance.
   *
   * @return The post2nodes.
   */
  public LblTree[] getPost2nodes()
  {
    return this.post2nodes;
  }

  /**
   * Gets the post2nodes for this instance.
   *
   * @param index The index to get.
   * @return The post2nodes.
   */
  public LblTree getPost2nodes(int index)
  {
    return this.post2nodes[index];
  }

  /**
   * Gets the postStrategy for this instance.
   * 
   * @return The postStrategy.
   */
  public final StratType[] getPostStrategy()
  {
    return this.postStrategy;
  }

  /**
   * Gets the postStrategy for this instance.
   * 
   * @param index
   *          The index to get.
   * @return The postStrategy.
   */
  public final StratType getPostStrategy(final int index)
  {
    return this.postStrategy[index];
  }

  /**
   * Returns the postorder of current root node.
   * 
   * @return current node.
   */
  public final int getCurrentNode()
  {
    return currentNode;
  }

  /**
   * Sets postorder of the current node in the recursion.
   * 
   * @param postorder
   *          postorder.
   */
  public final void setCurrentNode(final int postorder)
  {
    currentNode = postorder;
  }

  /**
   * Sets the switch state of the tree.
   * 
   * @param value
   *          new switch value.
   */
  public final void setSwitched(final boolean value)
  {
    switched = value;
  }

  /**
   * Returns switch state of a tree.
   * 
   * @return true if tree is switched and false otherwise.
   */
  public final boolean isSwitched()
  {
    return switched;
  }

  /**
   * Returns an array representation of a given path's type.
   * 
   * @param pathType
   *          path type
   * @return an array with a requested path
   */
  public final int[] getPath(final NodeType pathType)
  {
    return paths.get(pathType);
  }

  /**
   * Returns relevant subtrees for given node. Assuming that child v of given
   * node belongs to given path,
   * all children of given node are returned but node v.
   * 
   * @param pathType
   *          type of the path
   * @param nodePostorder
   *          postorder of a node
   * @return an array with relevant subtrees of a given node
   */
  public final int[] getNodeRelSubtrees(final NodeType pathType,
      final int nodePostorder)
  {
    return relSubtrees.get(pathType)[nodePostorder];
  }
}
